package likou.offer;

/**
 * @Info: 二维数组中的查找(从右往左找)
 * @Author: 唐小尊
 * @Date: 2020/7/30  17:00
 */
public class _04 {
    public static void main(String[] args) {
        System.out.println(findNumberIn2DArray(new int[][]{{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}}
                , 15));
    }

    public boolean findNumberIn2DArray1(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int row = 0, column = columns - 1;
        while (row < rows && column >= 0) {
            int num = matrix[row][column];
            if (num == target) {
                return true;
            } else if (num > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }


    public static boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                System.out.print(matrix[i][j] + " ");
            }
            System.out.println();
        }
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int min = Math.min(matrix.length, matrix[0].length);
        int i;
        if (min < 2) {
            if (matrix.length > min) {
                for (i = 0; i < matrix.length; i++) {
                    if (matrix[i][0] == target) {
                        return true;
                    }
                }
                return false;
            }
            for (i = 0; i < matrix[0].length; i++) {
                if (matrix[0][i] == target) {
                    return true;
                }
            }
            return false;
        }
        for (i = 0; i < min; i++) {
            if (matrix[i][i] >= target) {
                break;
            }
        }
        //不是n*n型的，需要重构数组，重新来过，最右下角的那一个，都小了，则往下面或者右边找
        if (i == min) {
            if (matrix.length == matrix[0].length) {
                return false;
            }
            return findNumberIn2DArray(qie(matrix, i), target);
        }
        if (matrix[i][i] == target) {
            return true;
        }
        if (i == 0) {
            return false;
        }
        for (int j = 0; j < i; j++) {
            if (matrix[i][j] == target || matrix[j][i] == target) {
                return true;
            }
        }
        return false;
    }

    //切分数组
    public static int[][] qie(int[][] matrix, int index) {
        //切断这个矩阵的已遍历部分。
        boolean p = true;//如果行多就为true
        int min = 0;
        if (matrix.length > matrix[0].length) {
            min = matrix[0].length;
        } else {
            min = matrix.length;
            p = false;
        }
        if (p) {
            int[][] newMatrix = new int[matrix.length - min][matrix[0].length];//行多减行
            for (int i = 0; i < newMatrix.length; i++) {
                System.arraycopy(matrix[index + i], 0, newMatrix[i], 0, newMatrix[0].length);
            }
            return newMatrix;
        }
        int[][] newMatrix = new int[matrix.length][matrix[0].length - min];//列多减列
        for (int i = 0; i < newMatrix[0].length; i++) {
            for (int j = 0; j < newMatrix.length; j++) {
                newMatrix[j][i] = matrix[i + index][j];
            }
        }
        return newMatrix;
    }
}
